package Hash;

import java.util.*;

class Student{
    public String id;

    public Student(String id){
        this.id = id;
    }

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Test {
    //寻找出现频率最大的前Top-k个数字
    public List<String> topKFrequent(String[] words, int k) {
        //1.通过循环遍历map统计每个单词出现的次数
        Map<String , Integer> map = new HashMap<>();
        for(String str : words){
            //当这个单词没有出现过时
            if (map.get(str) == null){
                map.put(str , 1);
            }else{   //当这个单词至少出现过一次时
                int val = map.get(str);  //先获取它出现的次数
                map.put(str,val+1);//然后在原来出现次数基础上加1
            }
        }

        //2.遍历map将map里面的 前K个元素  放到小根堆里面
        //堆里面的元素是map,即通过Entry调用map的key和val组成的整体
        PriorityQueue<Map.Entry<String , Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //存储时,如果两个key的val频率相同,应该找Key变为大根堆进行存储
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());  //通过比较器比较o1和o2,以value来比较,创建小根堆
            }
        });

        for(Map.Entry<String , Integer> entry : map.entrySet()){
            if(minHeap.size() < k){
                //如果堆里面的元素还没有放满
                //直接存到 小根堆中
                minHeap.offer(entry);
            }else{
                //如果堆满了,就比较遍历map的value和堆顶value值的大小,即比较他们的出现次数
                //获取堆顶map的value值
                Map.Entry<String , Integer> top = minHeap.peek();
                //比较堆顶的value和遍历map的val的大小关系
                if(top.getValue().compareTo(entry.getValue()) < 0){      //因为Integer是引用类型所以要用CompareTo这个方法来比较
                    //弹出堆顶元素
                    minHeap.poll();
                    //将当前出现次数比较多的map入堆
                    minHeap.offer(entry);
                }else{
                    //如果map中key出现的value(频率)相同,
                    if(top.getValue().compareTo(entry.getValue()) == 0){
                        //若频率相同,按字母顺序输出
                        if(top.getKey().compareTo(entry.getKey()) > 0){
                            //频率相同,字典序小的需要入堆
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //通过上面循环就能得到小根堆,但是题目要求我们返回的是单词频率由高到底的,所以还要对它进行反转
        List<String> ret = new ArrayList<>();
        for(int i = 0; i < k ; i++ ){
            Map.Entry<String , Integer> top = minHeap.poll();
            ret.add(top.getKey());//默认尾插
        }
        //反转链表
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        
    }

    //统计每个数字出现了多少次,下标为数字,值为下标这个字出现的次数
    public static Map<Integer , Integer> countNum(int[] arr){
        Map<Integer , Integer>  map = new HashMap<>();
        for(int i = 0 ; i < arr.length ; i++){
            if(map.get(arr[i]) == null){
                //当前数据未出现过
                map.put(arr[i] , 1);
            }else{
                //拆包
                int val = map.get(arr[i]);
                map.put(arr[i] , val+1);
            }
        }
        return map;
    }

    public static void main4(String[] args) {
        int[] arr = {1,1,3,4,5,7,5,6,8,9,1,2,3,3,4,5,6};
        Map<Integer , Integer> map = countNum(arr);
        //System.out.println(map);
          for(Map.Entry<Integer,Integer> entry : map.entrySet()){
              System.out.println("数字: "+entry.getKey()+"出现了 "+ entry.getValue()+" 次。");
          }
    }















    public static void main3(String[] args) {
        Map<String,Integer> map = new HashMap<>();

        Set<String> set = new HashSet<>();

        HashMap<String,Integer> map2 = new HashMap<>();

    }
    public static void main2(String[] args) {
        Student student = new Student("123456");
        int hashcode1 = student.hashCode();
        System.out.println(hashcode1);

        Student student2 = new Student("123456");
        int hashcode2 = student2.hashCode();
        System.out.println(hashcode2);
        System.out.println("====");
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();
        hashBuck2.push(student , 999);

        System.out.println(hashBuck2.get(student2));
    }


    public static void main1(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.push(4,888);
        hashBuck.push(1,888);
        hashBuck.push(2,888);
        hashBuck.push(3,888);
        hashBuck.push(5,888);
        hashBuck.push(6,888);
        hashBuck.push(7,888);
        hashBuck.push(8,888);
        hashBuck.push(9,888);

        hashBuck.push(144,100);

        System.out.println(hashBuck.get(144));


        System.out.println("===");
    }
}
